package com.llb666.java.leetcode;

import lombok.extern.slf4j.Slf4j;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by 斌~
 * 2021/4/28 18:31
 */
@Slf4j
public class 是否存在环形链表 {

    /**
     * 内部类 -- 链表节点
     */
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val,ListNode next){
            this.val =val;
            this.next =next;
        }
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        node5.next =node3;

        System.out.println(hasCycle(node1));
        boolean loopInListBySlowAndFastPointer = isLoopInListBySlowAndFastPointer(node1);
        log.info("快慢指针方式判断是否有环，结果是{}",loopInListBySlowAndFastPointer);
    }

    /**
     * 遍历方式：遍历结束，指针未找到为下一节点为null的节点，则表示有环
     * @param head 头节点
     * @return boolean
     */
    private static boolean hasCycle(ListNode head){
        Set<ListNode> set =new HashSet<>();
        while (head !=null){
            if( !set.add(head)){
                return true;
            }
            head =head.next;
        }
        return false;
    }

    /**
     * 让两个人尽速跑步，速度快的人能追上速度慢的，表示有环
     * @param head 头节点
     * @return boolean
     */
    private static boolean isLoopInListBySlowAndFastPointer(ListNode head) {
        if (head == null) { // head是指定链表的头指针
            return false;
        }
        ListNode slow = head; //慢指针
        ListNode fast = head.next; // 快指针
        while (fast != null && fast.next != null) {
            if (slow.equals(fast)) {
                return true;
            }
            slow = slow.next; //慢指针每次走一步
            fast = fast.next.next;  // 快指针每次走两步
        }

        return false;
    }
}
